#include <iostream>
#include "Algorithm/03_queue/linkQueue.h"
using namespace std;

#define MaxVertexNum 100 // ������Ŀ�����ֵ
#define INFINITY         // ����intֵ
typedef char VertexType; // �������������
typedef int EdgeType;    // ��Ȩͼ�б���Ȩֵ����������

///////////////ͼ�Ĵ洢--��Ӿ��� //////////////////////////////////////////
typedef struct
{
    VertexType Vex[MaxVertexNum];              // �����
    EdgeType Edge[MaxVertexNum][MaxVertexNum]; // ��Ӿ��󣬱߱�
    int vexnum, arcnum;                        // ͼ��ǰ�������ͱ�����������
} MGraph;

typedef struct
{
    VertexType Vex[MaxVertexNum];              // �����
    EdgeType Edge[MaxVertexNum][MaxVertexNum]; // ��Ӿ��󣬱߱�
    int vexnum, arcnum;                        // ͼ��ǰ�������ͱ�����������
} Graph;

///////////////ͼ�Ĵ洢--�ڽӱ���////////////////////////////////////////////////

// ����/����
typedef struct ArcNode
{
    int adjvex;           // ��/�� ָ���ĸ��ڵ�
    struct ArcNode *next; // ָ����һ������ָ��
                          // InfoType info; //��Ȩֵ
} ArcNode;

// ����
typedef struct VNode
{
    VertexType data; // ������Ϣ
    ArcNode *first;  // ��һ���ߣ�����
} VNode, AdjList[MaxVertexNum];

// ���ڽӱ��洢��ͼ
typedef struct
{
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

////////////////ͼ�Ĺ�����ȱ�����BFS��///////////////////////////////////

#define MAX_VERTEX_NUM 999
/// ���ʱ������
bool visited[MAX_VERTEX_NUM];

void visit(int v)
{
}

void Enqueue(LinkQueue q, int v)
{
}

int DeQueue(LinkQueue Q, int v)
{
}

int FirstNeighbor(Graph G, int v)
{
}

int NextNeighbor(Graph G, int v, int w)
{
}

LinkQueue Q;

/// ������ȱ���
void BFS(Graph G, int v)
{                      // �Ӷ���v������������ȱ���ͼG
    visit(v);          // ���ʳ�ʼ����v
    visited[v] = true; // ��v���ѷ��ʱ��
    Enqueue(Q, v);     // ����v�����Q
    while (!isEmpty(Q))
    {
        DeQueue(Q, v); // ����v������
        for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
        {
            // ���v�����ڽӵ�
            if (!visited[w])
            {                      // wΪv����δ���ʵ��ڽӶ���
                visit(w);          // ���ʶ���w
                visited[w] = true; // ��w���ѷ��ʱ��
                Enqueue(Q, w);
                // EnQueue(Q, w);     // ����w�����
            } // if
        } // while
    }
}

/// ��ͼG���й�����ȱ���
void BFSTraverse(Graph G)
{
    for (int i = 0; i < G.vexnum; ++i)
    {
        visited[i] = false; // ���ʱ�������ʼ��
    }
    InitQueue(Q); // ��ʼ����������Q
    for (int i = 0; i < G.vexnum; ++i)
    { // ��0�Ŷ��㿪ʼ����
        if (!visited[i])
        {              // ��ÿ����ͨ��������һ��BFS
            BFS(G, i); // viδ���ʹ�����vi��ʼBFS
        }
    }
}

///////////////////图的深度优先遍历///////////////////////////////////////////

/// @brief 从顶点出发，深度优先遍历图G
/// @param G
/// @param v
void DFS(Graph G, int v)
{
    visit(v);          // 访问顶点v
    visited[v] = true; // 设已访问标记
    for (int w = FirstNeighbor(G, v); w >= 0; w = NextNeighbor(G, v, w))
    {
        if (!visited[w])
        { // w为u的尚未访问的邻接顶点
            DFS(G, w);
        }
    }
}

/// @brief 对图G进行深度优先遍历
/// @param G
void DFSTraverse(Graph G)
{
    for (int v = 0; v < G.vexnum; ++v)
    {
        visited[v] = false; // 初始化 已访问标记数据
    }
    for (int v = 0; v < G.vexnum; ++v)
    { // 本代码中是从v=0开始遍历
        if (!visited[v])
        {
            DFS(G, v);
        }
    }
}

//////////////////////////BFS求最短路径/////////////////////////////////////////////
//适用于无权图或所有边权值相同的图
int d[];
int path[];
/// @brief 求顶点u到其他顶点的嘴短路径
/// @param G
/// @param u
void BFS_MIN_Distance(Graph G, int u)
{
    // d[i]表示从u到i节点的嘴短路径
    for (int i = 0; i < G.vexnum; ++i)
    {
        d[i] = -1;    // 初始化路径长度
        path[i] = -1; // 最短路径从哪个顶点过来
    }
    d[u] = 0;
    visited[u] = true;
    Enqueue(Q, u);
    while (!isEmpty(Q)) // BFS算法主过程
    {
        DeQueue(Q, u); // 对头元素u出队
        for (int w = FirstNeighbor(G, u); w >= 0; w = NextNeighbor(G, u, w))
        {
            if (!visited[w]) // w为u的尚未访问的邻接顶点
            {
                d[w] = d[u] + 1;   // 路径长度+1
                path[w] = u;       // 最短路径应从u到w
                visited[w] = true; // 设已访问标记
                Enqueue(Q, w);     // 顶点w入队
            } // if
        } // while
    }
}
